//给定一个正整数 n ，返回范围在 [0, n] 都非负整数中，其二进制表示不包含 连续的 1 的个数。 
//
// 
//
// 示例 1: 
//
// 
//输入: n = 5
//输出: 5
//解释: 
//下面是带有相应二进制表示的非负整数<= 5：
//0 : 0
//1 : 1
//2 : 10
//3 : 11
//4 : 100
//5 : 101
//其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。 
//
// 示例 2: 
//
// 
//输入: n = 1
//输出: 2
// 
//
// 示例 3: 
//
// 
//输入: n = 2
//输出: 3
// 
//
// 
//
// 提示: 
//
// 
// 1 <= n <= 10⁹ 
// 
// Related Topics动态规划 
//
// 👍 296, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.Arrays;

class NonNegativeIntegersWithoutConsecutiveOnes {
    public static void main(String[] args) {
        Solution solution = new NonNegativeIntegersWithoutConsecutiveOnes().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        char[] s;
        int[][] memo;

        // 数位DP
        public int findIntegers(int n) {
            s = Integer.toString(n, 2).toCharArray();
            int m = s.length;
            memo = new int[m][2];
            for (int i = 0; i < m; i++) {
                Arrays.fill(memo[i], -1);
            }
            return dfs(0, 0, true);
        }

        // prev表示前面一位的数字
        public int dfs(int i, int prev, boolean isLimit) {
            // 结束条件：到达此处的路径均为可行解，直接返回 1 即可
            if (i == s.length) return 1;
            if (!isLimit && memo[i][prev] != -1) return memo[i][prev];

            int up = isLimit ? s[i] - '0' : 1;
            int res = 0;
            for (int j = 0; j <= up; j++) {
                // 如果前面的数字不为1，当前的数字也不为1，才进行递归
                if (!(prev == 1 && j == 1)) {
                    res += dfs(i + 1, j, isLimit && j == up);
                }
            }

            if (!isLimit) memo[i][prev] = res;
            return res;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
